package main

import (
	"fmt"
)

//选择排序（Selection Sort）是一种简单直观的排序算法。其基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。
//选择排序的时间复杂度为 O(n^2)，其中 (n) 是待排序数组的长度。尽管选择排序的时间复杂度较高，但它具有实现简单、空间复杂度低（仅需要常数级别的额外空间）等优点。
//
//选择排序的基本步骤
//初始化：假设数组的第一个元素是已排序部分，其余部分是未排序部分。
//选择最小元素：从未排序部分中找到最小的元素。
//交换元素：将找到的最小元素与未排序部分的第一个元素交换位置。
//重复步骤2和3：将已排序部分的边界向右移动一位，重复上述过程，直到整个数组排序完成

// @Description: 选择排序  O(n^2)
func main() {
	var arr [10]int = [10]int{34, 6, 79, 66, 22, 43, 1, 25, 89, 7}
	fmt.Println(arr)
	sortMaxToMin(&arr)
	sortMinToMax(&arr)
}

// sortMaxToMin
//
//	@Description: 从最大到最小
//	@param arr
func sortMaxToMin(arr *[10]int) {
	var temp int
	for i := 0; i < len(*arr)-1; i++ { // 减少最后一次不必要的比较
		maxIndex := getMaxIndex(arr, i)
		if (*arr)[maxIndex] > (*arr)[i] { //交换
			temp = (*arr)[maxIndex]
			(*arr)[maxIndex] = (*arr)[i]
			(*arr)[i] = temp
		}
	}
	fmt.Println(*arr)
}

// getMaxIndex
//
//	@Description: 找到最大的下标
//	@param arr
//	@param start
//	@return int
func getMaxIndex(arr *[10]int, start int) int {
	maxIndex := start
	for i := start + 1; i < len(*arr); i++ { // 从 start+1 开始，减少一次不必要
		if (*arr)[i] > (*arr)[maxIndex] {
			maxIndex = i
		}
	}
	return maxIndex
}

// @return error 如果输入数组为空或长度不为10，则返回错误
func sortMinToMax(arr *[10]int) {
	for i := 0; i < len(*arr); i++ {
		minIndex := getMinIndex(arr, i)
		if (*arr)[minIndex] < (*arr)[i] {
			(*arr)[minIndex], (*arr)[i] = (*arr)[i], (*arr)[minIndex] // 交换 golang特有写法
		}
	}
	fmt.Println(*arr)
}

// getMinIndex 找到从 start 开始的最小元素的下标
//
// @param arr 指向固定大小为10的整数数组的指针
// @param start 开始查找的起始索引
// @return int 最小元素的下标
func getMinIndex(arr *[10]int, start int) int {
	minIndex := start
	for i := start + 1; i < len(*arr); i++ {
		if (*arr)[i] < (*arr)[minIndex] {
			minIndex = i
		}
	}
	return minIndex
}
